//
// Problem 1: gas stations (plus route plan)
//
// Created by tianq on 24-12-5.
//

#include <iostream>
#include <vector>
#include <random>
#include <unordered_map>
#include <ranges>
using namespace std;
using ull = unsigned long long;

int main() {
    int n, k;  // n: fuel tank size, k: gas stations count
    vector<int> distances; // distance[0] means road from station 0 (start) to station 1

    // cin >> n >> k;
    // for (int i = 0; i < k; i++){
    //     int tmp = 0;
    //     cin >> tmp;
    //     distances.emplace_back(tmp);
    // }

    // generate test data
    n = 100, k = 10;
    random_device rd;
    mt19937_64 rng(rd());
    uniform_int_distribution int_dist(0, n); // [0,n]: our car can not go further than tank capacity n
    for (int i = 0; i <= k; i++) // 0: start, [1,k]: gas station, k+1: destination, we stops there, so no further roads
        distances.push_back(int_dist(rng));

    // echo input
    cout << "problem 1 plus" << endl;
    cout << "tank size: " << n << endl;
    cout << "gas station count: " << k << endl;
    for (int i = 0; i <= k + 1; i++) cout << i << "\t";
    cout << endl;
    for (int i = 0; i <= k; i++) cout << "    " << distances[i] << "\t";
    cout << endl;

    // plus version, basically changing from a single counting number to a vector of station ids

    ull minRefill = numeric_limits<ull>::max();
    vector<int> bestRefills;
    unordered_map<int, vector<int> > map;
    map.emplace(n, 0); // <GasRemain: n, RefillList: {}> note that 0 here means 0 for initial capacity

    for (int i = 0; i < distances.size(); i++) {
        const int ahead = distances[i];
        minRefill = numeric_limits<ull>::max();
        unordered_map<int, vector<int> > newMap;
        for (const auto &[remain, refills]: map) {
            if (remain < ahead) continue;
            if (refills.size() < minRefill) minRefill = refills.size();
            if (int newRemain = remain - ahead;
                !newMap.contains(newRemain) || refills.size() < newMap[newRemain].size()) {
                newMap[newRemain] = refills;
            }
            if (!newMap.contains(n) || refills.size() + 1 < newMap[n].size()) {
                newMap[n] = refills; // since we are using const reference, we can't append Station ID here
                newMap[n].emplace_back(i + 1); // skipping 0, since we are leaving 0 for 1, the refill happens at 1
            }
        }
        map.swap(newMap);

        cout << endl << "ahead: " << ahead << ", min refill: " << minRefill << endl;
        for (const auto &[key, values]: map) {
            cout << "remain: " << key << ", \t total " << values.size() << " refills: ";
            for (const auto &val: values) cout << val << ", ";
            cout << endl;
        }
    }

    for (const auto &refills : map | std::views::values) {
        if (refills.size() > minRefill) continue;

        cout << endl << "result:" << endl;
        cout << "min refills: " << minRefill << endl;
        cout << "Station Ids: ";
        for (const int &id: refills)
            cout << id << ", ";
        cout << endl;

        break;
    }
    return 0; // a trailing return should be safer
}

